Esercitazione 2
Soluzioni passo-passo esercizi per casa
Esercizio 1.6: soluzione passo-passo
Ricordiamo la traccia dell'esercizio:
Scrivere un programma che, a partire dalla sezione
.datache segue (e scaricabile qui), conta e stampa il numero di occorrenze dinumeroinarray..include "./files/utility.s"
.data
array: .word 1, 256, 256, 512, 42, 2048, 1024, 1, 0
array_len: .long 9
numero: .word 1
Questa è invece la soluzione proposta dall'esercizio:
.include "./files/utility.s"
.data
array: .word 1, 256, 256, 512, 42, 2048, 1024, 1, 0
array_len: .long 9
numero: .word 1
.text
_main:
nop
mov $0, %cl
mov numero, %ax
mov $0, %esi
comp:
cmp array_len, %esi
je fine
cmpw array(%esi), %ax
jne poi
inc %cl
poi:
inc %esi
jmp comp
fine:
mov %cl, %al
call outdecimal_byte
ret
Come prima cosa, cerchiamo di capire, a grandi linee, cosa cerca di fare questo programma.
Notiamo l'uso di %cl: dall'inizializzazione a riga 12, l'incremento condizionato a righe 19-21, e la stampa a righe 28-29, si evince che %cl è usato come contatore dei successi, ossia di quante volte è stato trovato numero in array.
Notiamo che %ax viene inizializzato con numero e, prima della stampa, mai aggiornato.
Infine, %esi viene inizializzato a 0 e incrementato a fine di ogni ciclo, confrontandolo con array_len per determinare quando uscire dal loop.
Infine, a riga 19 notiamo il confronto tra un valore di array, indicizzato con %esi, e %ax, che contiene numero.
Si ricostruisce quindi questa logica: scorro valore per valore array, indicizzandolo con %esi, e lo confronto con numero, che è appoggiato su %ax (perché il confronto tra due valori in memoria non è possibile con cmp). Utilizzo %cl come contatore dei successi, e alla fine dello scorrimento ne stampo il valore.
Fin qui nessuna sorpresa, il programma sembra seguire lo schema che si seguirebbe con un normale programma in C:
int cl = 0;
for(int esi = 0; esi < array_len; esi++){
if(array[esi] == numero)
cl++;
}
Proviamo ad eseguire il programma: ci si aspetta che stampi 2. Invece, stampa 3. Dobbiamo passare al debugger.
Quello che ci conviene guardare è quello che succede ad ogni loop, in particolare alla riga 19, dove la cmpw confronta un valore di array con %ax, che contiene numero.
Però, la cmpw utilizza un indirizzamento complesso che, abbiamo visto, richiede una sintassi più complicata nel debugger.
Cambio quindi quella istruzione in una serie equivalente che sia più facile da osservare col debugger.
.include "./files/utility.s"
.data
array: .word 1, 256, 256, 512, 42, 2048, 1024, 1, 0
array_len: .long 9
numero: .word 1
.text
_main:
nop
mov $0, %cl
mov numero, %ax
mov $0, %esi
comp:
cmp array_len, %esi
je fine
movw array(%esi), %bx
cmpw %bx, %ax
jne poi
inc %cl
poi:
inc %esi
jmp comp
fine:
mov %cl, %al
call outdecimal_byte
ret
Assemblo, avvio il debugger, e setto un breakpoint alla riga 20 con break 20.
Lascio girare il programma con continue, che quasi immediatamente raggiunge la riga 20 e si ferma.
Ricordiamo che il debugger si ferma prima di eseguire una istruzione.
Vediamo lo stato dei registri, con i r ax bx cl esi.
(gdb) i r ax bx cl esi
ax 0x1 1
bx 0x1 1
cl 0x0 0
esi 0x0 0
Fin qui, tutto come ci si aspetta: %ax che contiene numero, %bx contiene il numero alla prima cella di array, i due contatori %cl e %esi sono a 0.
Facciamo step per vedere l'esito del confronto: dopo la riga 21 l'esecuzione giunge alla riga 22, indicando che il salto non è stato fatto perché jne è stata eseguita dopo un confronto tra valori uguali.
Continuiamo con step controllando che il comportamento sia quello atteso, fino a giungere di nuovo alla riga 20.
(gdb) i r ax bx cl esi
ax 0x1 1
bx 0x0 0
cl 0x1 1
esi 0x1 1
Qui abbiamo la prima sorpresa. In %bx troviamo 0, ma il secondo valore di array è 256.
Se continuiamo, vediamo che 256 compare come terzo valore, poi 1 come quarto, poi 256 come quinto.
Abbiamo quindi dei valori aggiuntivi che compaiono nel vettore mentre lo scorriamo ma non nell'allocazione codice a riga 4.
Continuando ancora, vediamo che i 9 valori coperti dal programma non sono affatto tutti e 9 quelli a riga 4, e che effettivamente il valore 1 compare 3 volte.
Abbiamo intanto confinato il problema: la lettura di valori da array.
Per capire cosa sta succedendo, dobbiamo ricordare come si comporta l'allocazione in memoria di valori su più byte: abbiamo infatti a che fare con word, composte da 2 byte ciascuna, e un indirizzo in memoria è l'indirizzo di un solo byte.
L'architettura x86 è little-endian, che significa little end first, un riferimento a I viaggi di Gulliver. Questo si traduce nel fatto che quando un valore di byte viene salvato in memoria a partire dall'indirizzo , il byte meno significativo del valore viene salvato in , il secondo meno significativo in , e così via fino al più significativo in .
Possiamo quindi immaginare così il nostro array in memoria.
Layout di array in memoria.
La lettura di una word dalla memoria funziona quindi così: dato l'indirizzo , vengono letti i byte agli indirizzi e e contatenati nell'ordine .
Una istruzione come movw a, %bx, quindi, salverà il contenuto di in %bh e il contenuto di in %bl.
Per la lettura di più word consecutive, dobbiamo assicurarci di incrementare l'indirizzo di 2 alla volta: come mostrato in figura, il secondo valore è memorizzato a partire da , il terzo da , e così via.
Tornando però al codice dell'esercizio, questo non succede:
comp:
cmp array_len, %esi
je fine
movw array(%esi), %bx
cmpw %bx, %ax
jne poi
inc %cl
poi:
inc %esi
jmp comp
Ecco quindi spiegato cosa legge il programma in memoria: quando alla seconda iterazione si esegue movb array(%esi), %bx, con %esi che vale 1, si sta leggendo un valore composto dal byte meno significativo del secondo valore concatenato con il byte più significativo del primo.
Questo valore è del tutto estraneo e privo di senso se confrontato con array così come è stato dichiarato e allocato, ma nell'eseguire le istruzioni il processore non controlla niente di tutto ciò.
Lettura erronea di array: sbagliando l'incremento dell'indirizzo, leggiamo dei byte senza alcuna relazione fra loro dalla memoria e li interpretiamo come parti di una word.
Abbiamo due strade per correggere questo errore.
Il primo approccio è quello di incrementare %esi di 2 alla volta, così che l'indirizzamente array(%esi) risulti corretto.
Questo però vuol dire che %esi non può più essere usato come contatore confrontabile con array_len, e si dovrà gestire tale confronto in altro modo (per esempio, usando un registro separato come contatore).
La seconda strada è quella di usare il fattore di scala dell'indirizzamento, che è pensato proprio per questi casi.
Infatti, array(, %esi, 2) calcolerà l'indirizzo .
Da notare la virgola subito dopo la parentesi, a indicare che non si sta specificando alcun registro base, mentre %esi è indice.
In ultimo, una riflessione sul codice C che abbiamo visto prima come modello di questo programma: in quel codice non vi è alcun errore perché array[esi], sfruttando la tipizzazione e l'aritmetica dei puntatori, applica sempre i fattori di scala corretti.
Il codice finale, scaricabile qui, è il seguente:
.include "./files/utility.s"
.data
array: .word 1, 256, 256, 512, 42, 2048, 1024, 1, 0
array_len: .long 9
numero: .word 1
.text
_main:
nop
mov $0, %cl
mov numero, %ax
mov $0, %esi
comp:
cmp array_len, %esi
je fine
cmpw array(, %esi, 2), %ax
jne poi
inc %cl
poi:
inc %esi
jmp comp
fine:
mov %cl, %al
call outdecimal_byte
ret
Esercizio 1.8: soluzione passo-passo
Ricordiamo la traccia dell'esercizio:
Scrivere un programma che svolge quanto segue.
# leggere 2 numeri interi in base 10, calcolarne il prodotto, e stampare il risultato.
# lettura:
# come primo carattere leggere il segno del numero, cioè un '+' o un '-'
# segue il modulo del numero, minore di 256
# stampa:
# stampare prima il segno del numero (+ o -), poi il modulo in cifre decimali
Questa è invece la soluzione proposta dall'esercizio:
.include "./files/utility.s"
mess1: .asciz "inserire il primo numero intero:\r"
mess2: .asciz "inserire il secondo numero intero:\r"
mess3: .asciz "il prodotto dei due numeri e':\r"
a: .word 0
b: .word 0
_main:
nop
lea mess1, %ebx
call outline
call in_intero
mov %ax, a
lea mess2, %ebx
call outline
call in_intero
mov %ax, b
mov a, %ax
mov b, %bx
imul %bx
lea mess3, %ebx
call outline
call out_intero
ret
# legge un intero composto da segno e modulo minore di 256
# ne lascia la rappresentazione in complemento alla radice base 2 in ax
in_intero:
push %ebx
mov $0, %bl
in_segno_loop:
call inchar
cmp $'+', %al
je in_segno_poi
cmp $'-', %al
jne in_segno_loop
mov $1, %bl
in_segno_poi:
call outchar
call indecimal_word
call newline
cmp $1, %bl
jne in_intero_fine
neg %ax
in_intero_fine:
pop %ebx
ret
# legge la rappresentazione di un numero intero in complemento alla radice base 2 in eax
# lo stampa come segno seguito dalle cifre decimali
out_intero:
push %ebx
mov %eax, %ebx
cmp $0, %ebx
ja out_intero_pos
jmp out_intero_neg
out_intero_pos:
mov $'+', %al
call outchar
jmp out_intero_poi
out_intero_neg:
mov $'-', %al
call outchar
neg %ebx
jmp out_intero_poi
out_intero_poi:
mov %ebx, %eax
call outdecimal_long
pop %ebx
ret
Per brevità, e vista la documentazione dei sottoprogrammi, lascio al lettore l'interpretazione a grandi linee del programma. Passeremo direttamente ai problemi incontrati testando il programma.
inserire il primo numero intero:
+30
Segmentation fault
L'errore, sicuramente già ben noto, è in realtà un risultato tipico di una vasta gamma di errori. Di per sé significa semplicemente "tentativo di accesso in una zona di memoria a cui non si può accedere per fare quello che si voleva fare". Non spiega, per esempio, cos'è che si voleva fare e perché è sbagliato.
Vediamo tramite il debugger.
Program received signal SIGSEGV, Segmentation fault.
_main () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:14
14 mov %ax, a
Vediamo che il problema è il tentativo di scrivere all'indirizzo , che è la word allocata poco più su.
Il problema qui è che il programma non ha nessuna distinzione tra .data e .text: di default è tutto .text, dove non si può scrivere perché non ci è permesso, normalmente, di sovrascrivere le istruzioni del programma.
.include "./files/utility.s"
.data
mess1: .asciz "inserire il primo numero intero:\r"
mess2: .asciz "inserire il secondo numero intero:\r"
mess3: .asciz "il prodotto dei due numeri e':\r"
a: .word 0
b: .word 0
.text
_main:
...
Riproviamo il programma:
inserire il primo numero intero:
+30
inserire il secondo numero intero:
+20
il prodotto dei due numeri e':
+600
Fin qui, sembra andare bene. Ricordiamoci però di testare tutti i casi di interesse, in particolare i casi limite. Le specifiche dell'esercizio ci chiedono di considerare numeri interi di modulo inferiore a 256.
inserire il primo numero intero:
+255
inserire il secondo numero intero:
+255
il prodotto dei due numeri e':
+65025
Corretto.
inserire il primo numero intero:
-255
inserire il secondo numero intero:
+255
il prodotto dei due numeri e':
+511
Decisamente non corretto.
Verifichiamo col debugger.
Per prima cosa, ci assicuriamo che la lettura di numeri negativi sia corretta.
Mettiamo un brekpoint a riga 16 (riga 14 prima dell'aggiunta di .data e .text), e verifichiamo cosa viene letto quando inseriamo -255.
(gdb) b 16
Breakpoint 2 at 0x56556774: file /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s, line 16.
(gdb) c
Continuing.
inserire il primo numero intero:
-255
Breakpoint 2, _main () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:16
16 mov %ax, a
(gdb) i r ax
ax 0xff01 -255
(gdb)
Fin qui è bene, il problema non sembra essere nella lettura di interi da tastiera.
Proseguiamo quindi alla moltiplicazione, e controlliamone il risultato.
La imul utilizzata è a 16 bit, che da documentazione vediamo usa %ax come operando implicito, %bx come operando esplicito, e %dx_%ax come destinatario del calcolo.
Breakpoint 3, _main () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:25
25 imul %bx
(gdb) i r ax bx
ax 0xff01 -255
bx 0xff 255
(gdb) s
27 lea mess3, %ebx
(gdb) i r dx ax
dx 0xffff -1
ax 0x1ff 511
(gdb)
Concatenando i due registri otteniamo 0xffff01ff, ricordando, in particolare per %ax, che gdb omette nelle stampe gli zeri all'inizio di esadecimali.
Possiamo verificare questo valore convertendo da esadecimale a decimale con una calcolatrice da programmatore: quella di Windows richiede prima di estendere il valore su 32 bit, cioè 0xffffffffffff01ff (ogni carattere esadecimale sono 4 bit e gli interi si estendono ripetendo il bit più significativo, vanno quindi aggiunte 8 f), altre calcolatrici permettono di specificare il numero di bit.
Il risultato è -65025, che è quello che ci aspettiamo.
Anche qui quindi è bene: resta la stampa di questo valore, cioè il sottoprogramma out_intero.
# legge la rappresentazione di un numero intero in complemento alla radice base 2 in eax
# lo stampa come segno seguito dalle cifre decimali
Vediamo qui la prima discrepanza: il sottoprogramma si aspetta il risultato in %eax, ma noi sappiamo che la imul lo lascia in %dx_%ax.
Ci si può chiedere quale dei due correggere, se il sottoprogramma o il programma che lo usa:
in generale, si cambiano le specifiche di un componente interno (il sottoprogramma) solo quando non hanno senso, mentre in questo caso abbiamo il componente esterno (il programma) che non rispetta le specifiche d'uso di quello interno.
Assicuriamoci quindi di lasciare il risultato nel registro giusto prima di call out_intero.
...
mov a, %ax
mov b, %bx
imul %bx
shl $16, %edx
movw %ax, %dx
movl %edx, %eax
lea mess3, %ebx
call outline
call out_intero
...
Riproviamo ad eseguire:
inserire il primo numero intero:
-255
inserire il secondo numero intero:
+255
il prodotto dei due numeri e':
+4294902271
Ritorniamo al debugger, cominciando dalla call di out_intero, verificando di avere il valore corretto in %eax.
Breakpoint 2, _main () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:33
33 call out_intero
(gdb) i r eax
eax 0xffff01ff -65025
(gdb)
Il valore è corretto. Proseguiamo quindi nel sottoprogramma, cercando di capire come funziona e dove potrebbe sbagliare.
La prima cosa che notiamo è che il sottoprogramma ha due rami, out_intero_pos e out_intero_neg, dove stampa segni diversi e, in caso di numero negativo, usa la neg per ottenere l'opposto.
Quando si giunge a out_intero_poi, stampa il modulo del numero usando outdecimal_long (che, ricordiamo, supporta solo numeri naturali).
Tuttavia, nella nostra esecuzione abbiamo un negativo che viene stampato come naturale.
Verifichiamo seguendo l'esecuzione con step, che entra nel sottoprogramma out_intero:
(gdb) s
out_intero () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:62
62 push %ebx
(gdb) s
63 mov %eax, %ebx
(gdb) s
64 cmp $0, %ebx
(gdb) i r ebx
ebx 0xffff01ff -65025
(gdb) s
65 ja out_intero_pos
(gdb) s
out_intero_pos () at /mnt/c/reti_logiche/assembler/lezioni/2/imul_debug.s:68
68 mov $'+', %al
(gdb)
Effettivamente, nonostante %ebx sia un numero negativo, il salto a out_intero_pos viene eseguito.
Guardiamo però meglio: l'istruzione di salto è ja, che interpreta il confronto come tra numeri naturali.
In effetti, qualunque valore di %ebx diverso da 0, se interpretato come naturale, risulta maggiore di 0.
Correggiamo quindi utilizzando jg, e ritestiamo.
cmp $0, %ebx
jg out_intero_pos
jmp out_intero_neg
inserire il primo numero intero:
-255
inserire il secondo numero intero:
+255
il prodotto dei due numeri e':
-65025
Si dovrebbe continuare con altri test (combinazioni di segni, uso di 0) fino a convincersi che funzioni, per questa lezione ci fermiamo qui.
Il codice finale, scaricabile qui, è il seguente:
.include "./files/utility.s"
.data
mess1: .asciz "inserire il primo numero intero:\r"
mess2: .asciz "inserire il secondo numero intero:\r"
mess3: .asciz "il prodotto dei due numeri e':\r"
a: .word 0
b: .word 0
.text
_main:
nop
lea mess1, %ebx
call outline
call in_intero
mov %ax, a
lea mess2, %ebx
call outline
call in_intero
mov %ax, b
mov a, %ax
mov b, %bx
imul %bx
shl $16, %edx
movw %ax, %dx
movl %edx, %eax
lea mess3, %ebx
call outline
call out_intero
ret
# legge un intero composto da segno e modulo minore di 256
# ne lascia la rappresentazione in complemento alla radice base 2 in ax
in_intero:
push %ebx
mov $0, %bl
in_segno_loop:
call inchar
cmp $'+', %al
je in_segno_poi
cmp $'-', %al
jne in_segno_loop
mov $1, %bl
in_segno_poi:
call outchar
call indecimal_word
call newline
cmp $1, %bl
jne in_intero_fine
neg %ax
in_intero_fine:
pop %ebx
ret
# legge la rappresentazione di un numero intero in complemento alla radice base 2 in eax
# lo stampa come segno seguito dalle cifre decimali
out_intero:
push %ebx
mov %eax, %ebx
cmp $0, %ebx
jg out_intero_pos
jmp out_intero_neg
out_intero_pos:
mov $'+', %al
call outchar
jmp out_intero_poi
out_intero_neg:
mov $'-', %al
call outchar
neg %ebx
jmp out_intero_poi
out_intero_poi:
mov %ebx, %eax
call outdecimal_long
pop %ebx
ret
Esercizio 2.1: esercizio d'esame 2022-01-26
Vediamo ora un esercizio d'esame, del 26 Gennaio 2022. Il testo con soluzione si trova qui.
Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.
La soluzione di questo esercizio ha alcuni spunti interessanti.
Il primo è che il set di dati è presentato come una matrice.
Ma a differenza del C dove possiamo scrivere matrice[i][j] e lasciare che l'aritmetica dei puntatori faccia il resto, in assember dobbiamo gestire da noi la rappresentazione di una matrice tramite un vettore, associando indici su due dimensioni ad un solo indice.
L'esercizio ci aiuta in questo indicando una associazione specifica, usata anche per il caricamento dello stato iniziale.
Da questa associazione osserviamo che: ogni lettera corrisponde a 4 celle consecutive, dove a corrisponde a , b a e così via.
Date le 4 celle consecutive, il numero determina una tra queste, dove 1 significa la prima, 2 la seconda e così via.
Se traduciamo la lettera in un indice e il numero in un indice , entrambi , possiamo esprimere quindi l'indice della cella nel vettore come .
Nella soluzione, i sottoprogrammi in_lettera e in_numero si occupano di leggere i due valori da tastiera (con la solita struttura ciclica per ignorare caratteri inattesi) e lasciare il relativo indice in %al.
Dato che i caratteri utilizzati sono consecutivi nella tabella ASCII, questi indici sono calcolabili con una semplice sottrazione.
# Sottoprogramma per la lettura della lettera, da 'a' a 'd'
# Lascia l'indice corrispondente (da 0 a 3) in AL
in_lettera:
call inchar
cmp $'a', %al
jb in_lettera
cmp $'d', %al
ja in_lettera
call outchar
sub $'a', %al
ret
Questi indici sono poi composti secondo la formula di cui sopra.
call in_lettera
mov %al, %cl
shl $2, %cl # cl = cl * 4, ossia la dimensione di ogni riga
call in_numero
add %al, %cl # cl contiene l'indice (da 0 a 15) della posizione bersagliata
Il secondo punto interessante è che non è necessario utilizzare un vettori di byte in memoria, perché per gestire un flag vero/falso basta un bit, e per gestirne 16 basta una word.
Tuttavia, non abbiamo modo di interagire con i registri in modo diretto sul singolo bit: possiamo immaginare una sintassi come %ax[%cl] che testi o modifichi uno specifico bit, ma il processore non ha nulla del genere.
Possiamo però utilizzare istruzioni bit a bit, con delle maschere adeguate che vadano a testare o modificare solo ciò che ci interessa.
Per il test, possiamo usare una and con una maschera composta da soli 0 tranne che per la posizione che ci interessa testare.
Se il risultato è diverso da 0, vuol dire che l'altro operando, alla posizione d'interesse, ha il bit 1.
mov $1, %ax
shl %cl, %ax # ax contiene una maschera da 16 bit con 1 nella posizione bersagliata
and %dx, %ax # se abbiamo colpito qualcosa, ax rimane invariato. altrimenti varra' 0
jz mancato
Similmente, quando intendiamo mettere un bit a 0 (in questo caso, a indicare che il bersaglio colpito non c'è più), possiamo usare una and con maschera opposta alla precedente, ossia con soli 1 tranne che per la posizione da azzerare, o una xor con la stessa maschera precedente, che causerà il cambio di valore (da 1 a 0 o da 0 a 1) solo del bit d'interesse.
La soluzione, dato che a questo punto è già noto che il bit di interesse è a 1, utilizza la seconda opzione.
colpito:
lea msg_colpito, %ebx
call outline
xor %ax, %dx # togliamo il bersaglio colpito
jmp ciclo_partita_fine
Questo schema rende tralaltro molto più semplice la lettura dello stato iniziale, dato che tutto il necesario è fatto dal sottoprogramma di utility inword.
Esercizi per casa
Esercizio 2.2
Quello che segue (e scaricabile qui) è un tentativo di soluzione per le seguenti specifiche:
# Leggere una riga dal terminale, che DEVE contenere almeno 2 caratteri '_'
# Identificare e stampa la sottostringa delimitata dai primi due caratteri '_'
Un esempio di output (qui in formato txt) è il seguente
questa e' una _prova_ !!
prova
Contiene tuttavia uno o più bug. Trovarli e correggerli.
.include "./files/utility.s"
.data
msg_in: .fill 80, 1, 0
.text
_main:
nop
mov $80, %cx
lea msg_in, %ebx
call inline
cld
mov $'_', %al
lea msg_in, %esi
mov $80, %cx
repne scasb
mov %esi, %ebx
repne scasb
mov %esi, %ecx
sub %ebx, %ecx
call outline
ret
Esercizio 2.3
A partire dalla soluzione dell'esercizio precedente, estendere il programma per rispettare le seguenti specifiche:
# Leggere una riga dal terminale
# Identificare e stampa la sottostringa delimitata dai primi due caratteri '_'
# Se un solo carattere '_' e' presente, assumere che la sottostringa cominci
# ad inizio stringa e finisca prima del carattere '_'
# Se nessun carattere '_' e' presente, stampare l'intera stringa